package interviewQuestions;
/**
 * 剑指offer12题 矩阵中的路径
 * 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
 * 路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。
 * 如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。
 * 例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
 *
 * [["a","b","c","e"],
 * ["s","f","c","s"],
 * ["a","d","e","e"]]
 *
 * 但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了
 * 矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。 
 *
 * 示例 1：
 *
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
 * 输出：true
 * 示例 2：
 *
 * 输入：board = [["a","b"],["c","d"]], word = "abcd"
 * 输出：false
 *
 *
 * */
public class WayofMatrix {
    /**
     * 思路：利用DFS + 剪枝解决
     * 递归参数：当前元素在矩阵board中的行列索引i和j，当前目标字符在word中的索引k
     *
     * 终止条件：
     * 返回false：1.行或列索引越界 2.当前矩阵的元素和目标元素不同 3.当前矩阵的元素被
     * 标记为已经访问过的元素
     *
     * 返回true：字符串word已经被全部匹配完成，即k=len(word) - 1.
     *
     * 递归工作：
     * 1.标记当前矩阵元素：将board[i][j]值暂存于变量tmp，并修改为字符'/'，代表此元素
     * 已经被访问过了
     * 2.搜索下一单元格：朝当前元素的下、左、右、上四个方向开始下一层递归，使用或连接
     * 代表只需要一条可行路径，并记录结果到res (这个顺序是可以打乱)
     * 3.还原当前矩阵元素：将tmp暂存值还原至board[i][j]元素
     *
     * 回溯返回值：返回res，代表是否搜索到了目标字符串
     * */

    public boolean exist (char[][] board, String word){
        char[] words = word.toCharArray(); // 将字符串转换成数组方便使用
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // k=0,每次都是从目标字符串头部开始检索
                if(dfs(board,words,i,j,0)) return true;
            }
        }
        return false;
    }

    /**
     * @param board 待查询的数组
     * @param word 目标字符串
     * @param i 当前元素在board数组中的行索引
     * @param j 当前元素在board数组中的列索引
     * @param k 当前元素在目标字符串word中的索引
     *
     * */
    public boolean dfs(char[][] board,char[] word,int i,int j,int k){

        /*-------------------- 先写终止条件 -----------------------*/
        // 越界的情况
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0){
            return false;
        }
        // 当前位置已经被访问过了 或 字符和目标字符不符合的情况
        if(word[k] != board[i][j]){
            return false;
        }
        // 字符串都匹配完成的情况
        if(k == word.length - 1) return true;

        /*----------------------- 然后开始递归工作 -----------------------*/
        // 将值赋值给一个临时变量然后标记已经访问过当前结点
        char tmp = board[i][j];
        board[i][j] = '/';
        boolean res = dfs(board,word,i+1,j, k+1) || dfs(board,word,i,j-1, k+1)
                || dfs(board,word,i,j+1, k+1) || dfs(board,word,i-1,j, k+1);
        board[i][j] = tmp;
        return res;
    }

    // main
    public static void main(String[] args) {
        WayofMatrix test = new WayofMatrix();
        boolean rs = test.exist(new char[][]{{'a', 'b'}, {'c', 'd'}}, "acdb");
        System.out.println(rs);
    }
}
